import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class demo1 {
   static char[]arr={'A','C','G','T'};
   static HashSet<String> stringHashSet;
   static int n;
    public  static int minMutation(String startGene, String endGene, String[] bank) {
        HashSet<String>hashSet=new HashSet<>();
        for(String temp:bank){
            hashSet.add(temp);
        }
        n=startGene.length();
         stringHashSet=new HashSet<>();
        return BFS(startGene,endGene,hashSet);
    }
    public static int BFS(String startGene,String endGene,HashSet hashSet){
        Queue<String>queue=new LinkedList<>();
        queue.add(startGene);
        int sum=0;
        while (!queue.isEmpty()){
            int size = queue.size();
            sum++;
            for (int j = 0; j <size ; j++) {
                String t=queue.poll();
                for (int i = 0; i <n ; i++) {
                    for (char temp : arr) {
                        //注意builder的创建地方  字符串t每次修改后需要刷新回去
                        StringBuilder builder = new StringBuilder(t);
                        builder.setCharAt(i, temp);
                        String s = builder.toString();
                        if (!stringHashSet.contains(s)) {
                            if(hashSet.contains(s)) {
                                if (s.equals(endGene)) return sum;
                                queue.add(s);
                            }
                            stringHashSet.add(s);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public  static int minMutation1(String startGene, String endGene, String[] bank) {
        HashSet<String>hashSet=new HashSet<>();
        for(String temp:bank){
            hashSet.add(temp);
        }
        n=startGene.length();
        stringHashSet=new HashSet<>();
        if(startGene.equals(endGene))return 0;
        if(hashSet.contains(endGene))return -1;
        return BFS1(startGene,endGene,hashSet);
    }
    public static int BFS1(String startGene,String endGene,HashSet hashSet){
        Queue<String>queue=new LinkedList<>();
        queue.add(startGene);
        int sum=0;
        while (!queue.isEmpty()){
            int size = queue.size();
            sum++;
            for (int j = 0; j <size ; j++) {
                String t=queue.poll();
                for (int i = 0; i <n ; i++) {
                    for (char temp : arr) {
                     char[] st=t.toCharArray();
                     st[i]=temp;
                     //（包括char[]）的toString()方法并未被重写，它继承自Object类的toString()方法，而Object类的toString()默认返回的是对象的内存地址相关的字符串
                        String s =new String(st);//不能使用st.toString();
                        if (!stringHashSet.contains(s)&&hashSet.contains(s)) {
                                if (s.equals(endGene)) return sum;
                                queue.add(s);
                            stringHashSet.add(s);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String a="AACCGGTT";
        String b="AACCGGTA";
        String[]arr={"AACCGGTA"};
        System.out.println(minMutation(a, b, arr));
    }
}
